Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Simplify Path

Problem Statement

Given an absolute file path in a Unix-style file system, simplify it by converting ".." to the previous directory and removing any "." or multiple slashes. The resulting string should represent the shortest absolute path.

Examples

Example 1

  • Input: path = "/a//b////c/d//././/.."
  • Expected Output: "/a/b/c"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • "." refers to the current directory and is ignored.
    • ".." moves up one directory, so "d" is removed.
    • The simplified path is "/a/b/c".

Example 2

  • Input: path = "/../"
  • Expected Output: "/"
  • Explanation:
    • ".." moves up one directory, but we are already at the root ("/"), so nothing happens.
    • The final simplified path remains "/".

Example 3

  • Input: path = "/home//foo/"
  • Expected Output: "/home/foo"
  • Explanation:
    • Convert multiple slashes (//) into single slashes (/).
    • The final simplified path is "/home/foo".

Constraints:

  • 1 <= path.length <= 3000
  • path consists of English letters, digits, period '.', slash '/' or '_'.
  • path is a valid absolute Unix path.

Solution

To simplify the path, we'll use a stack to track the directories we're currently in. We'll split the input path into components by the "/" character, then process each component one by one. If a component is "..", we go to the previous directory by popping the top of the stack. If a component is "." or an empty string, we do nothing. Otherwise, we push the component into the stack as a new directory.

Step-by-Step Algorithm

  1. Split the input path by the "/" character into an array of components.

  2. Initialize an empty stack.

  3. For each component in the array:

    • If the component is "..", pop the top of the stack (if it's not already empty).
    • Else if the component is "." or an empty string, do nothing.
    • Else, push the component into the stack as a new directory.
  4. Merge all elements in the stack into a string by reversing the order and joining them with the '/' character. Ensure the final path starts with '/' to represent an absolute path.

Algorithm walkthrough

Image
  1. Initialize a Stack: A Stack<String> is created to store components of the simplified path.

  2. Split the Path: The input path "/a//b////c/d//././/.." is split using "/" as the delimiter. The resulting parts are: ["", "a", "", "b", "", "", "", "c", "d", "", ".", "", ".", "", "", ".."]. Empty strings and dots (".") represent the current directory and will be ignored in further processing.

  3. Process Each Part:

    • First Part (""): It's empty, so it's ignored.
    • Second Part ("a"): It's a directory name and is pushed onto the stack.
    • Third Part (""): Ignored.
    • Fourth Part ("b"): Another directory name, pushed onto the stack.
    • Next Several Parts ("", "", ""): All empty, so ignored.
    • Part "c": A directory name, pushed onto the stack.
    • Part "d": Another directory name, pushed onto the stack.
    • Part ".": Represents the current directory, ignored.
    • Part "." (again): Again, represents the current directory, ignored.
    • Last Part (".."): Represents moving up one directory. It pops "d" from the stack.

    After processing, the stack contains: ["a", "b", "c"].

  4. Reconstruct Simplified Path: Next, create the resulting string by joining all stack elements with the '/' character in reverse order.

    • After processing the stack, the string contains "/a/b/c".
  5. Return the Result:

    • For the given input, the output is "/a/b/c".

Code

Here is the code for this algorithm:

Java

. . . .

Complexity Analysis

Time Complexity

  • Splitting the path: The input string path is split using / as the delimiter, which takes time, where N is the length of the input string path. This creates an array of strings representing the components of the path.

  • Processing the components: The algorithm processes each component of the path array. For each component, it either pushes it onto the stack, pops an element from the stack, or skips the component if it is . or empty. Since each component is processed at most once, this takes time in total.

  • Building the result: After processing all components, the algorithm reconstructs the simplified path by concatenating the elements in the stack. This also takes time.

Overall time complexity: , where N is the length of the input string path.

Space Complexity

  • Stack space: The stack stores the components of the simplified path. In the worst case, the stack contains all components of the path, which requires space.

  • Result string space: The result string is used to store the final result which also takes space, as it holds the result of the same size as the input string (in the worst case).

Overall space complexity: .

Simplify Path (medium)
Next Permutation (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity